package org.example.Soution001;


import java.util.ArrayList;
import java.util.List;

public class FlattenTreeNode {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);
        FlattenTreeNode node = new FlattenTreeNode();
        node.flatten(root);
        System.out.println(root.right.right.right.val+" "+root.right.right.right.right.val+" "+root.right.right.right.right.right.val);
    }

    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flattenTree(root);
    }

    public List<TreeNode> flattenTree(TreeNode root) {
        //0是根节点，1是lastNode节点
        List<TreeNode> res = new ArrayList<TreeNode>();
        if (root == null) return res;
        //让它的左右子树变成单链表
        List<TreeNode> left = flattenTree(root.left);
        List<TreeNode> right = flattenTree(root.right);
        //实行插入大计
        res.add(root);
        root.left = null;
        root.right = null;
        if (left.size() > 0) {
            root.right=left.get(0);
            if (right.size() > 0) {
                left.get(1).right=right.get(0);
                res.add(right.get(1));
            }else{
                res.add(left.get(1));
            }
        }else{
            if(right.size() > 0){
                root.right=right.get(0);
                res.add(right.get(1));
            }else{
                res.add(root);
            }
        }
        return res;
    }
}
